/**
 * 文件名：quickSort.ts
 * 文件描述：实现快速排序
 *
 * 实现思路：
 *      1. 首先通过三个指针，left，right，middle，找到三个节点，并进行排序交换，最后结果是arr[left] <= arr[middle] <= arr[right]
 *      2. 以middle为枢纽，令arr[middle] 与 arr[right - 1] 进行互换
 *      3. 令 i = left，j = right - 1，i负责递增寻找第一个大于枢纽值的下标，j负责递减寻找第一个小于枢纽值的下标
 *      4. 判断i < j，如果不是则退出，如果是的话则换位
 *      5. 将arr[i] 与 arr[right - 1]（枢纽） 进行换位
 *      6. 以[left, i - 1]，[i + 1,right]为参数，分别进行快速排序
 * */

// 引入swap
import swap from "./swap";

// 实现查找枢纽的函数，即完成步骤1，2
function median(left: number, right: number, arr: Array<number>) {
	// 步骤一：排序交换
	const middle = Math.floor((left + right) / 2);
	if (arr[left] > arr[middle]) {
		swap(left, middle, arr);
	}
	if (arr[middle] > arr[right]) {
		swap(middle, right, arr);
	}
	if (arr[left] > arr[middle]) {
		swap(left, middle, arr);
	}
	// 步骤二：将枢纽放到最后
	swap(middle, right - 1, arr);

	// 返回枢纽的值
	return arr[right - 1];
}

// 快速排序
function quickSort(arr: Array<number>) {
	quick(0, arr.length - 1, arr);
	return arr;
}

// quick函数，实现步骤3，4，5，6
function quick(left: number, right: number, arr: Array<number>) {
	// 设置终止条件
	if (left >= right) return;

	// 获取枢纽值并且完成步骤1，2
	const pivot = median(left, right, arr);
	// 步骤3：定义i，j指针。        注意：left和right - 1此时的值分别为小于pivot的值和pivot
	let i = left,
		j = right - 1;

	// 进入循环
	while (true) {
		while (arr[++i] < pivot) {}
		while (arr[--j] > pivot) {}
		if (i > j) {
			break;
		} else {
			swap(i, j, arr);
		}
	}

	// 执行步骤5：将枢纽更新到指定位置
	swap(i, right - 1, arr);

	// 递归执行
	quick(left, i - 1, arr);
	quick(i + 1, right, arr);
}


// 测试
console.log(quickSort([3, 6, 8, 10, 1, 2, 1]))